{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Build Binary Expression Tree From Infix Expression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #string #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #字符串 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: expTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #根据中缀表达式构造二叉表达式树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>二叉表达式树</strong> 是一种表达算术表达式的二叉树。二叉表达式树中的每一个节点都有零个或两个子节点。&nbsp;叶节点（有 0 个子节点的节点）表示操作数，非叶节点（有 2 个子节点的节点）表示运算符：&nbsp;<code>'+'</code>&nbsp;（加）、&nbsp;<code>'-'</code> （减）、&nbsp;<code>'*'</code> （乘）和&nbsp;<code>'/'</code> （除）。</p>\n",
    "\n",
    "<p>对于每一个运算符为 <code>o</code> 的非叶节点，对应的<strong> <a href=\"http://baike.baidu.com/item/中缀表达式/2725244?fr=aladdin\" target=\"_blank\">中缀表达式</a></strong> 为&nbsp;<code>(A o B)</code>，其中&nbsp;<code>A</code>&nbsp;是左子树所表达的表达式，&nbsp;<code>B</code>&nbsp;是右子树所表达的表达式。</p>\n",
    "\n",
    "<p>给定一个<strong> 中缀表达式 </strong>字符串&nbsp;<code>s</code>，其中包含操作数、上面提到的运算符，以及括号&nbsp;<code>'('</code>&nbsp;与&nbsp;<code>')'</code>&nbsp;。</p>\n",
    "\n",
    "<p>返回一个有效的<strong> 二叉表达式树</strong>，其 <a href=\"http://baike.baidu.com/item/中序遍历/757281?fr=aladdin\" target=\"_blank\"><strong>中序遍历</strong></a><sup> </sup>序列对应表达式 <code>s</code> 消除括号后的序列（详情参见下面的示例）<em>。</em></p>\n",
    "\n",
    "<p><strong>注意，表达式的一般解析顺序适用于&nbsp;</strong><code>s</code>，即优先解析括号内的表达式，然后解析乘除法，最后解析加减法。</p>\n",
    "\n",
    "<p>同时，操作数在 <code>s</code> 和树的中序遍历中 <strong>出现顺序相同</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/02/ex1-4.png\" style=\"width: 250px; height: 161px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"3*4-2*5\"\n",
    "<strong>输出：</strong>[-,*,*,3,4,2,5]\n",
    "<strong>解释：</strong>上面是唯一一种有效的二叉表达式树，其中序遍历生成 s 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/02/ex1-2.png\" style=\"width: 150px; height: 210px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"2-3/(5*2)+1\"\n",
    "<strong>输出：</strong>[+,-,1,2,/,null,null,null,null,3,*,null,null,5,2]\n",
    "<strong>解释：</strong>上面的树的中序遍历为 2-3/5*2+1 ，与 s 消除括号后相同。该树还会生成正确的结果，其操作数的顺序与 s 中出现的顺序相同。\n",
    "下面的树也是一个有效的二叉表达式树，具有与 s 相同的中序遍历，但它不是一个有效的答案，因为它的求值结果不同。\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/02/ex1-1.png\" style=\"width: 201px; height: 281px;\" />\n",
    "下面的树也是无效的。尽管它的计算结果相等并与上述树等效，但其中序遍历不会产生 s ，并且其操作数与 s 中的顺序也不相同。\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/02/ex1-3.png\" style=\"width: 281px; height: 281px;\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"1+2+3+4+5\"\n",
    "<strong>输出：</strong>[+,+,5,+,4,null,null,+,3,null,null,1,2]\n",
    "<strong>解释：</strong>二叉树 [+,+,5,+,+,null,null,1,2,3,4] 也是诸多有效的二叉表达式树之一。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 100</code></li>\n",
    "\t<li><code>s</code>&nbsp;中包含数字和字符&nbsp;<code>'+'</code>、&nbsp;<code>'-'</code>、&nbsp;<code>'*'</code>、&nbsp;<code>'/'</code> 。</li>\n",
    "\t<li><code>s</code>&nbsp;中的操作数 <strong>恰好</strong> 是一位数字。</li>\n",
    "\t<li>题目数据保证 <code>s</code> 是一个有效的表达式。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [build-binary-expression-tree-from-infix-expression](https://leetcode.cn/problems/build-binary-expression-tree-from-infix-expression/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [build-binary-expression-tree-from-infix-expression](https://leetcode.cn/problems/build-binary-expression-tree-from-infix-expression/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"3*4-2*5\"', '\"2-3/(5*2)+1\"', '\"1+2+3+4+5\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expTree(self, s: str) -> 'Node':\n",
    "        signs = set(list(\"+-*/\"))\n",
    "        flag = any((ch in signs) for ch in s)\n",
    "        if not flag: return Node(s)\n",
    "        def parse(s, ops):\n",
    "            cnt = 0\n",
    "            for i in range(len(s) - 1, -1, -1):\n",
    "                    if s[i] == ')':\n",
    "                        cnt += 1\n",
    "                    elif s[i] == '(':\n",
    "                        cnt -=1\n",
    "                    if cnt == 0 and s[i] in ops:\n",
    "                        root = Node(s[i])\n",
    "                        root.left = self.expTree(s[:i])\n",
    "                        root.right = self.expTree(s[i+1:])\n",
    "                        return root\n",
    "\n",
    "        if first := parse(s, set(list(\"+-\"))):\n",
    "            return first\n",
    "        elif second := parse(s, set(list(\"*/\"))):\n",
    "            return second\n",
    "        return self.expTree(s[1:-1])\n",
    "\n",
    "    \n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expTree(self, s: str) -> 'Node':\n",
    "        priority={'(':0,'*':1,'/':1,'+':2,'-':2}\n",
    "        n=len(s)\n",
    "        nums=[]\n",
    "        ops=[]\n",
    "        i=0\n",
    "        while i<n:\n",
    "            if s[i] in ['0','1','2','3','4','5','6','7','8','9']:\n",
    "                start=i\n",
    "                while i<len(s) and s[i] in ['0','1','2','3','4','5','6','7','8','9']:\n",
    "                    i+=1\n",
    "                nums.append(Node(val=s[start:i]))\n",
    "                continue\n",
    "            elif s[i]=='(':\n",
    "                ops.append(Node(val='('))\n",
    "            elif s[i]==')':\n",
    "                while len(ops)>0 and priority[ops[-1].val]>0:\n",
    "                    y=nums.pop()\n",
    "                    x=nums.pop()\n",
    "                    op=ops.pop()\n",
    "                    op.left=x\n",
    "                    op.right=y\n",
    "                    nums.append(op)\n",
    "                ops.pop()\n",
    "            else:\n",
    "                while len(ops)>0 and ops[-1].val!='(' and priority[ops[-1].val]<=priority[s[i]]:\n",
    "                    y=nums.pop()\n",
    "                    x=nums.pop()\n",
    "                    op=ops.pop()\n",
    "                    op.left=x\n",
    "                    op.right=y\n",
    "                    nums.append(op)\n",
    "                ops.append(Node(val=s[i]))\n",
    "            i+=1\n",
    "        while len(ops)>0:\n",
    "            y=nums.pop()\n",
    "            x=nums.pop()\n",
    "            op=ops.pop()\n",
    "            op.left=x\n",
    "            op.right=y\n",
    "            nums.append(op)\n",
    "        return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expTree(self, s: str) -> 'Node':\n",
    "\n",
    "\n",
    "        priority = {\n",
    "            \"(\": 0,\n",
    "            \"*\": 1,\n",
    "            \"/\": 1,\n",
    "            \"+\": 2,\n",
    "            \"-\": 2\n",
    "        }\n",
    "\n",
    "        nums, opts = [], []\n",
    "\n",
    "        cur = 0\n",
    "\n",
    "        while cur < len(s):\n",
    "\n",
    "            if s[cur].isdigit():\n",
    "                temp = cur\n",
    "                while cur < len(s) and s[cur].isdigit():\n",
    "                    cur += 1\n",
    "                nums.append(Node(s[temp: cur]))\n",
    "                continue\n",
    "            elif s[cur] == \"(\":\n",
    "                opts.append(Node(\"(\"))\n",
    "            elif s[cur] == \")\":\n",
    "\n",
    "                while opts and priority[opts[-1].val] > 0:\n",
    "                    y, x, opt = nums.pop(), nums.pop(), opts.pop()\n",
    "                    opt.left, opt.right = x, y\n",
    "                    nums.append(opt)\n",
    "                opts.pop()\n",
    "            # 运算符\n",
    "            else:\n",
    "\n",
    "                while opts and opts[-1].val != \"(\" and priority[opts[-1].val] <= priority[s[cur]]:\n",
    "                    y, x, opt = nums.pop(), nums.pop(), opts.pop()\n",
    "                    opt.left, opt.right = x, y\n",
    "                    nums.append(opt)\n",
    "                opts.append(Node(s[cur]))\n",
    "            cur += 1\n",
    "        \n",
    "        while opts:\n",
    "            y, x, opt = nums.pop(), nums.pop(), opts.pop()\n",
    "            opt.left, opt.right = x, y\n",
    "            nums.append(opt)\n",
    "        return nums[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expTree(self, s: str) -> 'Node':\n",
    "\n",
    "\n",
    "\n",
    "        priority = {\n",
    "            \"(\": 0,\n",
    "            \"*\": 1,\n",
    "            \"/\": 1,\n",
    "            \"+\": 2,\n",
    "            \"-\": 2\n",
    "        }\n",
    "\n",
    "        nums, opts = [], []\n",
    "\n",
    "        cur = 0\n",
    "\n",
    "        while cur < len(s):\n",
    "\n",
    "            if s[cur].isdigit():\n",
    "                temp = cur\n",
    "                while cur < len(s) and s[cur].isdigit():\n",
    "                    cur += 1\n",
    "                nums.append(Node(s[temp: cur]))\n",
    "                continue\n",
    "            elif s[cur] == \"(\":\n",
    "                opts.append(Node(\"(\"))\n",
    "            elif s[cur] == \")\":\n",
    "\n",
    "                while opts and priority[opts[-1].val] > 0:\n",
    "                    y, x, opt = nums.pop(), nums.pop(), opts.pop()\n",
    "                    opt.left, opt.right = x, y\n",
    "                    nums.append(opt)\n",
    "                opts.pop()\n",
    "            # 运算符\n",
    "            else:\n",
    "\n",
    "                while opts and opts[-1].val != \"(\" and priority[opts[-1].val] <= priority[s[cur]]:\n",
    "                    y, x, opt = nums.pop(), nums.pop(), opts.pop()\n",
    "                    opt.left, opt.right = x, y\n",
    "                    nums.append(opt)\n",
    "                opts.append(Node(s[cur]))\n",
    "            cur += 1\n",
    "        \n",
    "        while opts:\n",
    "            y, x, opt = nums.pop(), nums.pop(), opts.pop()\n",
    "            opt.left, opt.right = x, y\n",
    "            nums.append(opt)\n",
    "        return nums[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expTree(self, s: str) -> 'Node':\n",
    "        signs = \"+-*/\"\n",
    "        flag = any((ch in signs) for ch in s)\n",
    "        if not flag: return Node(s)\n",
    "        cnt = 0\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "                if s[i] == ')':\n",
    "                    cnt += 1\n",
    "                elif s[i] == '(':\n",
    "                    cnt -=1\n",
    "                if cnt == 0 and s[i] in \"+-\":\n",
    "                    root = Node(s[i])\n",
    "                    root.left = self.expTree(s[:i])\n",
    "                    root.right = self.expTree(s[i+1:])\n",
    "                    return root\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "                if s[i] == ')':\n",
    "                    cnt += 1\n",
    "                elif s[i] == '(':\n",
    "                    cnt -=1\n",
    "                if cnt == 0 and s[i] in \"*/\":\n",
    "                    root = Node(s[i])\n",
    "                    root.left = self.expTree(s[:i])\n",
    "                    root.right = self.expTree(s[i+1:])\n",
    "                    return root\n",
    "        return self.expTree(s[1:-1])\n",
    "\n",
    "    \n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    priority = {\n",
    "        \"+\": 1, \"-\": 1, \"*\": 2, \"/\": 2, \"(\": 0,\n",
    "    }\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.operate = []\n",
    "        self.numbers = []\n",
    "\n",
    "    def expTree(self, s: str) -> 'Node':\n",
    "        s = list(self.trim(s))\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "\n",
    "        while i < n:\n",
    "            c = s[i]\n",
    "\n",
    "            if c.isdigit():\n",
    "                j = i\n",
    "                while j < n and s[j].isdigit():\n",
    "                    j += 1\n",
    "                token = ''.join(s[i:j])\n",
    "                self.numbers.append(Node(token))\n",
    "                i = j - 1\n",
    "            elif c == '(':\n",
    "                self.operate.append(c)\n",
    "            elif c == ')':\n",
    "                while self.operate and self.operate[-1] != '(':\n",
    "                    self.calculate()\n",
    "                self.operate.pop()\n",
    "            elif c in \"+-*/\":\n",
    "                while self.operate and self.priority[self.operate[-1]] >= self.priority[c]:\n",
    "                    self.calculate()\n",
    "                self.operate.append(c)\n",
    "\n",
    "            i += 1\n",
    "\n",
    "        while self.operate:\n",
    "            self.calculate()\n",
    "\n",
    "        return self.numbers[-1]\n",
    "\n",
    "    def trim(self, s: str) -> str:\n",
    "        s = s.replace(\" \", \"\")\n",
    "        s = s.replace(\"(+\", \"(0+\")\n",
    "        s = s.replace(\"(-\", \"(0-\")\n",
    "        if s and s[0] == \"-\":\n",
    "            s = \"0\" + s\n",
    "        return s\n",
    "\n",
    "    def calculate(self):\n",
    "        p = self.operate.pop()\n",
    "        b = self.numbers.pop()\n",
    "        a = self.numbers.pop()\n",
    "        node = Node(str(p), a, b)\n",
    "        self.numbers.append(node)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expTree(self, s: str) -> 'Node':\n",
    "        signs = \"+-*/\"\n",
    "        flag = any((ch in signs) for ch in s)\n",
    "        if not flag: return Node(s)\n",
    "        def parse(s, ops):\n",
    "            cnt = 0\n",
    "            for i in range(len(s) - 1, -1, -1):\n",
    "                    if s[i] == ')':\n",
    "                        cnt += 1\n",
    "                    elif s[i] == '(':\n",
    "                        cnt -=1\n",
    "                    if cnt == 0 and s[i] in ops:\n",
    "                        root = Node(s[i])\n",
    "                        root.left = self.expTree(s[:i])\n",
    "                        root.right = self.expTree(s[i+1:])\n",
    "                        return root\n",
    "\n",
    "        if first := parse(s, \"+-\"):\n",
    "            return first\n",
    "        elif second := parse(s, \"*/\"):\n",
    "            return second\n",
    "        return self.expTree(s[1:-1])\n",
    "\n",
    "    \n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expTree(self, s: str) -> 'Node':\n",
    "        priority = {\"(\":0, \"*\":1, \"/\":1, \"+\":2, \"-\":2}\n",
    "        nums, opts = [], []\n",
    "        cur = 0 \n",
    "        while cur < len(s):\n",
    "            #所有入栈的元素都是节点\n",
    "            if s[cur].isnumeric():  #数字直接入栈\n",
    "                temp = cur\n",
    "                while cur < len(s) and s[cur].isnumeric():\n",
    "                    cur += 1\n",
    "                nums.append(Node(val = s[temp:cur]))\n",
    "                continue\n",
    "            elif s[cur] == '(':  #左括号直接入栈\n",
    "                opts.append(Node(val = \"(\"))\n",
    "            elif s[cur] == ')':   #把括号内的全部算完\n",
    "                while len(opts) > 0 and priority[opts[-1].val] > 0:\n",
    "                    y, x, opt = nums.pop(), nums.pop(), opts.pop()\n",
    "                    opt.left, opt.right = x, y\n",
    "                    nums.append(opt)\n",
    "                opts.pop()   #去掉左括号\n",
    "            else:\n",
    "                #把上一个左括号前优先级比自己大或等于自己的算完\n",
    "                while len(opts) > 0 and opts[-1].val != '(' and priority[opts[-1].val] <= priority[s[cur]]:\n",
    "                    y, x, opt = nums.pop(), nums.pop(), opts.pop()\n",
    "                    opt.left, opt.right = x, y\n",
    "                    nums.append(opt)\n",
    "                opts.append(Node(val = s[cur]))\n",
    "            cur += 1\n",
    "\n",
    "        #按序处理剩下的\n",
    "        while len(opts) > 0:\n",
    "            y, x, opt = nums.pop(), nums.pop(), opts.pop()\n",
    "            opt.left, opt.right = x, y\n",
    "            nums.append(opt)\n",
    "        return nums[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expTree(self, s: str) -> 'Node':\n",
    "\n",
    "        node_list = []\n",
    "        index = 0\n",
    "        flag_list = [\"(\"]\n",
    "        rank_dict = {\"-\":1,\"+\":1,\"*\":2,\"/\":2, \"(\":3}\n",
    "\n",
    "        def compare_flag(a):\n",
    "            while True:\n",
    "                if  (a==\")\"):\n",
    "                    if (flag_list[-1]==\"(\"):\n",
    "                        flag_list.pop(-1)\n",
    "                        break\n",
    "                    else:\n",
    "                        node_list.append(Node(flag_list.pop(-1)))\n",
    "                else:\n",
    "                    if (flag_list[-1]==\"(\") or (rank_dict[a]>rank_dict[flag_list[-1]]):\n",
    "                        flag_list.append(a)\n",
    "                        break\n",
    "                    else:\n",
    "                        node_list.append(Node(flag_list.pop(-1)))\n",
    "\n",
    "        while index<len(s):\n",
    "            if s[index] in \"1234567890\":\n",
    "                cur_s_num = \"\"\n",
    "                while (index<len(s)) and  (s[index] in \"1234567890\"):\n",
    "                    cur_s_num += s[index]\n",
    "                    index += 1\n",
    "                node_list.append(Node(cur_s_num))\n",
    "            else:\n",
    "                compare_flag(s[index])\n",
    "                index += 1\n",
    "\n",
    "        while len(flag_list)>1:\n",
    "            node_list.append(Node(flag_list.pop(-1)))\n",
    "        # print([cur_node.val for cur_node in node_list])\n",
    "\n",
    "\n",
    "        num_list = []\n",
    "        before_node = None\n",
    "        for cur_node in node_list:\n",
    "            cur_s = cur_node.val\n",
    "            if rank_dict.get(cur_s):\n",
    "                cur_node.right = num_list.pop(-1)\n",
    "                cur_node.left = num_list.pop(-1)\n",
    "            num_list.append(cur_node)\n",
    "        return num_list[-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expTree(self, s: str) -> 'Node':\n",
    "        priority = {\"(\":3, \"*\":1, \"/\":1, \"+\":2, \"-\":2}\n",
    "        nums, opts = [], []\n",
    "        cur = 0 \n",
    "        while cur < len(s):\n",
    "            #所有入栈的元素都是节点\n",
    "            if s[cur].isnumeric():  #数字直接入栈\n",
    "                temp = cur\n",
    "                while cur < len(s) and s[cur].isnumeric():\n",
    "                    cur += 1\n",
    "                nums.append(Node(val = s[temp:cur]))\n",
    "                continue\n",
    "            elif s[cur] == '(':  #左括号直接入栈\n",
    "                opts.append(Node(val = \"(\"))\n",
    "            elif s[cur] == ')':   #把括号内的全部算完\n",
    "                while len(opts) > 1 and opts[-1].val != '(':\n",
    "                    y, x, opt = nums.pop(), nums.pop(), opts.pop()\n",
    "                    opt.left, opt.right = x, y\n",
    "                    nums.append(opt)\n",
    "                opts.pop()   #去掉左括号\n",
    "            else:\n",
    "                #把上一个左括号前优先级比自己大或等于自己的算完\n",
    "                while len(opts) > 0 and priority[opts[-1].val] <= priority[s[cur]]:\n",
    "                    y, x, opt = nums.pop(), nums.pop(), opts.pop()\n",
    "                    opt.left, opt.right = x, y\n",
    "                    nums.append(opt)\n",
    "                opts.append(Node(val = s[cur]))\n",
    "            cur += 1\n",
    "\n",
    "        #按序处理剩下的\n",
    "        while len(opts) > 0:\n",
    "            y, x, opt = nums.pop(), nums.pop(), opts.pop()\n",
    "            opt.left, opt.right = x, y\n",
    "            nums.append(opt)\n",
    "        return nums[0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
